package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/jump-game-iii/'>跳跃游戏 III(Jump Game III)</a>
 * <p>这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。</p>
 * <p>请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。</p>
 * <p>注意，不管是什么情况下，你都无法跳到数组之外。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：arr = [4,2,3,0,3,1,2], start = 5
 *      输出：true
 *      解释：
 *          到达值为 0 的下标 3 有以下可能方案：
 *          下标 5 -> 下标 4 -> 下标 1 -> 下标 3
 *          下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
 *
 *  示例 2：
 *      输入：arr = [4,2,3,0,3,1,2], start = 0
 *      输出：true
 *      解释：
 *          到达值为 0 的下标 3 有以下可能方案：
 *          下标 0 -> 下标 4 -> 下标 1 -> 下标 3
 *
 *  示例 3：
 *      输入：arr = [3,0,2,1,2], start = 2
 *      输出：false
 *      解释：无法到达值为 0 的下标 1 处。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= arr.length <= 5 * 10^4</li>
 *     <li>0 <= arr[i] < arr.length</li>
 *     <li>0 <= start < arr.length</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/17 16:15
 */
public class LC1306JumpGame_III_M {
    static class Solution {
        public boolean canReach(int[] arr, int start) {
            return dfs(arr, start, new boolean[arr.length]);
            //return bfs(arr, start);
        }

        private boolean bfs(int[] arr, int start) {
            int n = arr.length;
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(start);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer cur = queue.poll();
                    if (cur < 0 || cur >= n || visited[cur]) {
                        continue;
                    }
                    if (arr[cur] == 0) {
                        return true;
                    }
                    visited[cur] = true;
                    queue.offer(cur + arr[cur]);
                    queue.offer(cur - arr[cur]);
                }
            }
            return false;
        }

        private boolean dfs(int[] arr, int currIdx, boolean[] visited) {
            if (arr[currIdx] == 0) {
                return true;
            }
            if (visited[currIdx]) {
                return false;
            }
            visited[currIdx] = true;
            // 向前跳跃
            if (currIdx - arr[currIdx] >= 0 && dfs(arr, currIdx - arr[currIdx], visited)) {
                return true;
            }
            // 向后跳跃
            if (currIdx + arr[currIdx] < arr.length && dfs(arr, currIdx + arr[currIdx], visited)) {
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.canReach(new int[]{4, 2, 3, 0, 3, 1, 2}, 5));
        System.out.println(solution.canReach(new int[]{4, 2, 3, 0, 3, 1, 2}, 0));
        System.out.println(solution.canReach(new int[]{3, 0, 2, 1, 2}, 2));
    }
}
